1. Field of the Invention
This invention relates to data processing systems employing virtual memory partitioned into pages, and, more specifically, to synchronizing apparatus for page replacement control where the central processing unit (CPU) and the input-output (I/O) devices share a common address translation mechanism, including a primary page directory.
2. Description of the Prior Art
In a computer system employing virtual memory, any reference to data or instructions which do not reside in main storage causes a fixed size block of data or instructions (called a page) to be moved from the secondary storage into the main storage. In order to make room for the new page in main storage, some other page may have to be moved back to the secondary storage. The algorithm used to select which page is moved back is called the replacement algorithm. Typically, a "least-recently-used" algorithm is used to govern movement of pages from main to secondary storage. That is, pages which have not recently been referenced are replaced first. Although the present discussion only concerns page movement between two storage levels, main and secondary storage, the basic concept of the invention is applicable to storage hierarchies with several levels (e.g., cache, main storage, disk, library). In such multi-level systems, if a page is not used for an extended period of time, it will migrate through the storage hierarchy to the slowest level.
The least-recently-used algorithm is acceptable for most paging situations. The most recently used data is contained in high-speed, main storage ready for immediate access, while less frequently used data resides in secondary, slower speed storage. Situations arise, however, in which certain data and instructions on certain pages must be available for immediate access in main storage independent of the usage history of the pages. Access to these pages may be required as a result of a reference made by either the CPU or by an I/O device. For example, data buffers for certain high speed I/O devices must be located in main storage. If part of a buffer must be fetched from slower speed storage after a data transfer has been started, the result could be to "overrun" the device, by a failure to provide the necessary buffer in time for part of the data transfer. As a second example, representative of a CPU requirement rather than an I/O device requirement, certain routines, called deadline-time processing routines, must execute within a set period of time in order to avoid some catastrophic result. Process control operations are typical of this type or routine. For these routines, the delay caused by fetching a page from secondary storage can be intolerable. In still other cases, it is desirable from either a performance or functional viewpoint to have certain high priority instruction routines or data always available in main storage.
There are several known techniques for insuring the presence of or "pinning" a page of data or instructions in main storage. The usual technique used to accomplish this is to reserve an area in main storage for those pages which cannot be permitted to migrate to secondary storage. Any attempt to replace a page pinned in this reserved storage is blocked. This approach works well as long as the reserved area is neither large nor has a dynamically changing size requirement. In a multi-tasking environment with a large number of tasks, the pages which must be pinned in main storage change, depending upon which tasks are executing. To provide an area large enough to contain all of the pages for all of the tasks would soon consume the entire main storage. Thus, some mechanism is needed to dynamically control which pages are to be pinned and to identify when a page can be unpinned. One arrangement for dynamic control of pinning and unpinning of pages which appears in the prior art is found in "Minimizing Input/Output Page Pinning In a Virtual Storage Data Processor" by J. K. Boggs, Jr., in IBM Technical Disclosure Bulletin Vol. 19, No. 1, June 1976.
This arrangement employs special virtual address translation hardware for each I/O channel and permits each I/O channel to pin only, while unpinning must be performed by the operating system. Accordingly, cost and efficiency disadvantages may be present in some applications. Another arrangement, described in U.S. Pat. No. 3,839,706 issued to Borchsenius, permits the I/O channel to both pin and unpin pages. In this arrangement a special channel look-aside buffer is used, and the zero/non-zero status of a page use counter is transmitted to memory to notify the CPU of the pinning. Extra channel hardware is required, and address translation means are duplicated. Arrangements allowing a CPU to pin and unpin pages are also known; however, the known arrangements operate in an environment in which page pinning by I/O devices does not occur.